function Node2() {
  this.key = 0
  this.color  = 1
  this.left = null 
  this.right = null
}

const NTL = new Node2()

function Node(key = 0 , color = 1, left = NTL, right = NTL) {
  this.key = key
  this.color = color  // 0: 红色, 1 黑色, 2 double black 双黑
  this.left = left
  this.right = right
}

function RedBlackTree(rootKey) {
  this.root = new Node(rootKey, 1)
}

RedBlackTree.prototype.has_red_child = function(root) {
  return root.left.color == 0 || root.right.color == 0
}


RedBlackTree.prototype.left_rotate = function(root) {
  // 这样的操作真的有点那种味道在里面真的没有话说..
  let temp  =  root.right
  root.right = temp.left
  temp.left = root
  return temp 
}


RedBlackTree.prototype.right_rotate = function(root) {
  let temp  =  root.left
  root.left = temp.right
  temp.right = root
  return temp 
}


RedBlackTree.prototype.insert_maintain = function(root) {
  console.log(root)
  let flag = 0
  // 进行判定
  if(root.left.color == 0 && this.has_red_child(root.left)) flag = 1
  if(root.right.color == 0 && this.has_red_child(root.right)) flag = 2
  if(flag == 0) return root
  // 插入的第一种情况 =>  父节点和叔叔节点都是一个红色的
  if(root.left.color == 0 && root.right.color == 0) {
    root.color = 0
    root.left.color = root.right.color = 1
    return root
  }
  // 表示我的红色重复节点在一个左子树
  if(flag == 1) {
    // 判断是LL 还是LR
    if(root.left.right.color == 0) {
      root.left = this.left_rotate(root.left)
    }
    root = this.right_rotate(root)
  } else {
    if(root.right.left.color == 0) {
      root.right = this.right_rotate(root.right)
    }
    root = this.left_rotate(root)
  }
  // 整体的下沉操作!
  root.color = 0
  root.left.color = root.right.color = 1
  return root
}

RedBlackTree.prototype.getNewNode = function(key) {
  // 默认是一个红色的操作
  return new Node(key,0)
}

RedBlackTree.prototype.__insert =  function(root, key) {
  if(root == NTL) return this.getNewNode(key)
  if(root.key == key) return root
  if(key < root.key) root.left = this.__insert(root.left, key)
  else root.right = this.__insert(root.right, key)
  // 进行一个插入的维护操作
  return  this.insert_maintain(root)
}

RedBlackTree.prototype.insert = function(root, key) {
  root = this.__insert(root,key)
  root.color = 1
  // 感觉搞成一个对象一样的操作才是一个正确的打开方式
  return this.root = root
}

RedBlackTree.prototype.__erase = function (root, key) {
  // console.log(key)
  if(root === NTL) return root
  if(root.key > key) root.left = this.__erase(root.left, key)
  else if(root.key < key) root.right = this.__erase(root.right, key)
  else {
     // 这个和平衡二叉树的操作都是一样的 ,, 这里一点点的代码就可以处理红黑树的始终情况
    //  console.log(root.val)
     if(root.left === NTL || root.right === NTL) {
       let temp = root.left ? root.left : root.right
      temp.color += root.color
      root = NTL
       return temp
     } else {
       let temp = this.predecessor(root)
       root.key = temp.key
       root.left = this.__erase(root.left, temp.key)
     }
  }
  return this.erase_maintain(root)
}
RedBlackTree.prototype.predecessor = function(root) {
  let temp = root.left
  while(temp.right !== NTL) temp = temp.right
  return temp
}

/* 红黑树的重点操作?  去除*/
RedBlackTree.prototype.erase_maintain = function(root) {
  // 注意这是一个在递归操作中进行的操作 => 所有这一步会发生在所有的从叶子节点开始的操作
  if(root.left.color !==2 && root.right.color !== 2) return root
  let flag = 0
  // 如果存在红色节点
  if(this.has_red_child(root)) {
    root.color = 0
    if(root.left.color == 0) root = this.right_rotate(root), flag = 1
    else root = this.left_rotate(root), flag = 2
    root.color = 1
    if(flag == 1) root.right = this.erase_maintain(root.right)
    else root.left = this.erase_maintain(root.left)
    return root
  }
  // 出现了插入调整的第一种情况
  if(root.left.color == 1 && !this.has_red_child(root.left)
    || (root.right.color == 1 && !this.has_red_child(root.right))) {
      root.left.color -= 1
      root.right.color -= 1
      // 根节点发生了变化
      root.color += 1
      return root
  }
  // 这就就证明 => 双重黑在右边
  if(root.left.color == 1) {
    // 去除了双重黑 这个里面都是纯看一个推理解决问题的
    root.right.color = 1
    if(root.left.left.color !== 0) {
      root.left.color = 0
      root.left = this.left_rotate(root.left)
      root.left.color = 1
    }
    // console.log(root.left.color, root.color)
    root.left.color = root.color
    root = this.right_rotate(root)
  } else {
    root.left.color = 1
    if(root.right.right.color !== 0) {
      root.right.color = 0
      root.right = this.right_rotate(root.left)
      root.right.color = 1
    }
    root.right.color = root.color
    root = this.left_rotate(root)
  }
  root.left.color = root.right.color = 1
  return root
}

RedBlackTree.prototype.erase = function(root, key) {
  root = this.__erase(root, key)
  root.color = 1
  return this.root = root
}




RedBlackTree.prototype.clear = function(root) {
  if(root == null) return
  this.clear(root.left)
  this.clear(root.right)
  root = null
  return
}


let temp = new RedBlackTree(5)

temp.insert(temp.root,9)
temp.insert(temp.root,8)
temp.insert(temp.root,3)
temp.insert(temp.root,2)
temp.insert(temp.root,4)
temp.insert(temp.root,1)
temp.insert(temp.root,7)

// temp.erase(temp.root, 1)
temp.erase(temp.root, 9)


// console.log(JSON.stringify(temp.root, null, 2))